package org.lql.algo.codecrush.week006;

/**
 * @author: liangqinglong
 * @date: 2025-08-07 17:52
 * @description: 面试题 17.14. 最小K个数 <a href="https://leetcode.cn/problems/smallest-k-lcci/description/">...</a>
 **/
public class SmallestK {

	/**
	 * 设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
	 * <p>
	 * 示例：
	 * <p>
	 * 输入： arr = [1,3,5,7,2,4,6,8], k = 4
	 * 输出： [1,2,3,4]
	 * 提示：
	 * <p>
	 * 0 <= len(arr) <= 100000
	 * 0 <= k <= min(100000, len(arr))
	 */
	public int[] smallestK(int[] arr, int k) {
		if (arr == null || arr.length == 0 || k == 0) {
			return new int[0];
		}
		if (k >= arr.length) {
			// Defensive copy
			int[] res = new int[arr.length];
			System.arraycopy(arr, 0, res, 0, arr.length);
			return res;
		}
		quickSelect(arr, 0, arr.length - 1, k);
		int[] res = new int[k];
		System.arraycopy(arr, 0, res, 0, k);
		return res;
	}

	// Quickselect to ensure first k elements are the smallest k (in any order)
	private void quickSelect(int[] arr, int left, int right, int k) {
		if (left >= right) return;
		int pivotIndex = partition(arr, left, right);
		if (pivotIndex == k) {
			return;
		} else if (pivotIndex > k) {
			quickSelect(arr, left, pivotIndex - 1, k);
		} else {
			quickSelect(arr, pivotIndex + 1, right, k);
		}
	}

	// Partition function: places pivot at correct position, all <= left, > right
	private int partition(int[] arr, int left, int right) {
		int pivot = arr[right];
		int i = left;
		for (int j = left; j < right; j++) {
			if (arr[j] <= pivot) {
				int tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				i++;
			}
		}
		int tmp = arr[i];
		arr[i] = arr[right];
		arr[right] = tmp;
		return i;
	}
}
